// 17.4 随机数
/**
 * 在新标准出现之前，C和C++都依赖于一个简单的C库函数rand来生成随机数。此函数生成均匀分布的伪随机整数，每个随机数的范围在0和一个系统相关的最大值（至少为32767）之间。
 * rand函数有一些问题：即使不是大多数，也有很多程序需要不同范围的随机数。一些应用需要随机浮点数。一些程序需要非均匀分布的数。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;
#include <functional>
#include "../VisualStudio2012/15/Quote.h"
#include "../VisualStudio2012/12/TextQuery.h"
#include <tuple>
#include <bitset>
#include <regex>
#include <random>
#include <cmath>

int main()
{
    // 17.4 随机数
    /*定义在头文件random中的随机数库通过一组协作的类来解决这些问题：随机数引擎类（random-number engines）和随机数分布类（random-number distribution）。表17.14描述了这些类。
        一个引擎类可以生成unsigned随机数序列，一个分布类使用一个引擎类生成指定类型的、在给定范围内的、服从特定概率分布的随机数。
表17.14 随机数库的组成
引擎      类型，生成随机unsigned整数序列
分布      类型，使用引擎返回服从特定概率分布的随机数
      C++程序不应该使用库函数rand，而应使用default_random_engine类和恰当的分布类对象。
    */

    // 17.4.1 随机数引擎和分布
    /*随机数引擎是函数对象类（参见14.8节，第506页），它们定义了一个调用运算符，该运算符不接受参数并返回一个随机unsigned整数。我们可以通过调用一个随机数引擎对象来生成原始随机数：
    */
    default_random_engine e; // 生成随机无符号数
    for(size_t i=0; i<10; ++i)
      cout << e() << " "; // e()“调用”对象来生成下一个随机数
    /*标准库定义了多个随机数引擎类，区别在于性能和随机性质量不同。每个编译器都会指定其中一个作为default_random_engine类型。此类型一般具有最常用的特性。
        表17.15列出了随机数引擎操作，标准库定义的引擎类型列在附录A.3.2（第783页）中。
表17.15 随机数引擎操作
Engine e;                默认构造函数，使用该引擎类型默认的种子
Engine e(s);             使用整型值s作为种子
e.seed(s)                使用种子s重置引擎状态
e.min()                  此引擎可生成的最小值和最大值
e.max()
Engine::result_type      此引擎生成的unsigned整型类型
e.discard(u)             将引擎推进n步，u的类型为unsigned long long
      对于大多数场合，随机数引擎的输出是不能直接使用的，这也是为什么早先我们称之为原始随机数。问题出在生成的随机数的值范围通常与我们需要的不符，而正确转换随机数的范围是极其困难的。
    */

    // 分布类型和引擎
    /*为了得到在一个指定范围内的数，我们使用一个分布类型的对象：[插图]
    */
    uniform_int_distribution<unsigned> u(0,9); // 生成0~9之间均匀分布的随机数
    default_random_engine e; // 生成无符号随机整数
    for(size_t i=0; i<10; ++i)
      cout << u(e) << " "; // 将u作为随机数源；每个调用返回在指定范围内并服从均匀分布的值
    /*类似引擎类型，分布类型也是函数对象类。分布类型定义了一个调用运算符，它接受一个随机数引擎作为参数。分布对象使用它的引擎参数生成随机数，并将其映射到指定的分布。
    当我们说随机数发生器时，是指分布对象和引擎对象的组合。
    */

    // 比较随机数引擎和rand函数
    /*对熟悉C库函数rand的读者，值得注意的是：调用一个default_random_engine对象的输出类似rand的输出。随机数引擎生成的unsigned整数在一个系统定义的范围内，而rand生成的数的范围在0到RAND_MAX之间。
        一个引擎类型的范围可以通过调用该类型对象的min和max成员来获得：[插图]
    */
    cout << "min: " << e.min() << " max: " << e.max() << endl;

    // 引擎生成一个数值序列
    /*随机数发生器有一个特性经常会使新手迷惑：即使生成的数看起来是随机的，但对一个给定的发生器，每次运行程序它都会返回相同的数值序列。
        序列不变这一事实在调试时非常有用。但另一方面，使用随机数发生器的程序也必须考虑这一特性。
      作为一个例子，假定我们需要一个函数生成一个vector，包含100个均匀分布在0到9之间的随机数。我们可能认为应该这样编写此函数：
// 几乎肯定是生成随机整数vector的错误方法
// 每次调用这个函数都会生成相同的100个数
vector<unsigned> bad_randVec()
{
  default_random_engine e;
  umiform_int_distribution<unsigned> u(0,9);
  vector<unsigned> ret;
  for(size_t i=0; i<100; ++i)
    ret.push_back(u(e));
  return ret;
}
      但是，每次调用这个函数都会返回相同的vector：
vector<unsigned> v1(bad_randVec());
vector<unsigned> v2(bad_randVec());
// 将打印“equal”
cout << ((v1==v2) ? "equal" : "not equal") << endl;
      编写此函数的正确方法是将引擎和关联的分布对象定义为static的（参见6.1.1节，第185页）：[插图]
// 返回一个vecotr，包含100个均匀分布的随机数
vector<unsigned> good_randVec()
{
  // 由于我们希望引擎和分布对象保持状态，因此应该将他们定义为static的，从而每次调用都生成新的数
  static default_random_engine e;
  static uniform_int_distribution<unsigned> u(0,9);
  vector<unsigned> ret;
  for(size_t i=0; i<100; ++i)
    ret.push_back(u(e));
  return ret;
}      
      由于e和u是static的，因此它们在函数调用之间会保持住状态。第一次调用会使用u（e）生成的序列中的前100个随机数，第二次调用会获得接下来100个，依此类推。
      一个给定的随机数发生器一直会生成相同的随机数序列。一个函数如果定义了局部的随机数发生器，应该将其（包括引擎和分布对象）定义为static的。否则，每次调用函数都会生成相同的序列。
    */
    
    // 设置随机数发生器种子
    /*随机数发生器会生成相同的随机数序列这一特性在调试中很有用。但是，一旦我们的程序调试完毕，我们通常希望每次运行程序都会生成不同的随机结果，可以通过提供一个种子（seed）来达到这一目的。
        种子就是一个数值，引擎可以利用它从序列中一个新位置重新开始生成随机数。
      为引擎设置种子有两种方式：在创建引擎对象时提供种子，或者调用引擎的seed成员：[插图]
default_random_engine e1;        // 引擎e1使用默认的种子
default_random_engine e2(1701);  // 引擎e2使用1701作为种子
// e3和e4将生成相同的序列，因为它们使用了相同的种子
default_random_engine e3;        // 使用默认种子
e3.seed(32767);                  // 调用seed设置一个新种子值
default_random_engine e4(32767); // 将种子设置为32767
for(size_t i=0; i!=100; ++i) {
  if(e1() == e2())
    cout << "unseeded match at iteration: " << i << endl;
  if(e3() != e4())
    cout << "seeded differs at iteration: " << i << endl;
}
      本例中我们定义了四个引擎。前两个引擎e1和e2的种子不同，因此应该生成不同的序列。后两个引擎e3和e4有相同的种子，它们将生成相同的序列。
      选择一个好的种子，与生成好的随机数所涉及的其他大多数事情相同，是极其困难的。可能最常用的方法是调用系统函数time。这个函数定义在头文件ctime中，它返回从一个特定时刻到当前经过了多少秒。
        函数time接受单个指针参数，它指向用于写入时间的数据结构。如果此指针为空，则函数简单地返回时间：[插图] default_random_engine e1(time(0)); // 稍微随机些的种子
        由于time返回以秒计的时间，因此这种方式只适用于生成种子的间隔为秒级或更长的应用。
    */
    default_random_engine e1(time(0)); // 稍微随机些的种子
    // 如果程序作为一个自动过程的一部分反复运行，将time的返回值作为种子的方式就无效了；它可能多次使用的都是相同的种子。

    // 17.4.2 其他随机数分布
    /*随机数引擎生成unsigned数，范围内的每个数被生成的概率都是相同的。而应用程序常常需要不同类型或不同分布的随机数。标准库通过定义不同随机数分布对象来满足这两方面的要求，
        分布对象和引擎对象协同工作，生成要求的结果。表17.16列出了分布类型所支持的操作。
    */

    // 生成随机实数
    /*程序常需要一个随机浮点数的源。特别是，程序经常需要0到1之间的随机数。最常用但不正确的从rand获得一个随机浮点数的方法是用rand（）的结果除以RAND_MAX，
        即，系统定义的rand可以生成的最大随机数的上界。这种方法不正确的原因是随机整数的精度通常低于随机浮点数，这样，有一些浮点值就永远不会被生成了。
      使用新标准库设施，可以很容易地获得随机浮点数。我们可以定义一个uniform_real_distribution类型的对象，并让标准库来处理从随机整数到随机浮点数的映射。
        与处理uniform_int_distribution一样，在定义对象时，我们指定最小值和最大值：[插图]
    */
    default_random_engine e; // 生成无符号随机整数
    uniform_real_distribution<double> u(0,1); // 0~1的均匀分布
    for(size_t i=0; i!=10; ++i)
      cout << u(e) << " ";

    // 使用分布的默认结果类型
    /*每个分布模板都有一个默认模板实参（参见16.1.3节，第594页）。生成浮点值的分布类型默认生成double值，而生成整型值的分布默认生成int值。由于分布类型只有一个模板参数，
        因此当我们希望使用默认随机数类型时要记得在模板名之后使用空尖括号（参见16.1.3节，第594页）：[插图]
    */
    // 空<>表示我们希望使用默认结果类型
    uniform_real_distribution<> u(0,1); // 默认生成double值

    // 生成非均匀分布的随机数
    /*除了正确生成在指定范围内的数之外，新标准库的另一个优势是可以生成非均匀分布的随机数。实际上，新标准库定义了20种分布类型，这些类型列在附录A.3（第781）中。
      作为一个例子，我们将生成一个正态分布的值的序列，并画出值的分布。由于normal_distribution生成浮点值，我们的程序使用头文件cmath中的lround函数将每个随机数舍入到最接近的整数。
        我们将生成200个数，它们以均值4为中心，标准差为1.5。由于使用的是正态分布，我们期望生成的数中大约99%都在0到8之间（包含）。
    */
    default_random_engine e;               // 生成随机整数
    normal_distribution<double> n(4, 1.5); // 均值4，标准差1.5
    vector<unsigned> vals(9);              // 9个元素均为0
    for(size_t i=0; i!=200; ++i) {
      unsigned v = lround(n(e)); // 舍入到最接近的整数
      if(v < vals.size())        // 如果结果在范围内
        ++vals[v];               // 统计每个结果出现的次数
    }
    for(size_t j=0; j!=vals.size(); ++j)
      cout << j << ": " << string(vals[j], '*') << endl;

    // bernoulli_distribution类
    /*我们注意到有一个分布不接受模板参数，即bernoulli_distribution，因为它是一个普通类，而非模板。此分布总是返回一个bool值。它返回true的概率是一个常数，此概率的默认值是0.5。
      作为一个这种分布的例子，我们可以编写一个程序，这个程序与用户玩一个游戏。为了进行这个游戏，其中一个游戏者——用户或是程序——必须先行。
        我们可以用一个值范围是0到1的uniform_int_distribution来选择先行的游戏者，但也可以用伯努利分布来完成这个选择。假定已有一个名为play的函数来进行游戏，我们可以编写像下面这样的循环来与用户交互：
    */
    string resp;
    default_random_engine e;    // e应保持状态，所以必须在循环外定义！
    bernoulli_distribution b;   // 伯努利分布，默认是50/50的机会
    do {
      bool first = b(e); // 如果为true，则程序先行
      cout << (first ? "We go first" : "You go first") << endl;
      // 传递谁先行的指示，进行游戏
      // cout << ((paly(first)) ? "sorry, you lost" : "congrats, you won" << endl;
      cout << "play again? Enter 'yes' or 'no'" << endl;
    } while(cin >> resp && resp[0] == 'y');
    /*由于引擎返回相同的随机数序列（参见17.4.1节，第661页），所以我们必须在循环外声明引擎对象。否则，每步循环都会创建一个新引擎，从而每步循环都会生成相同的值。
        类似的，分布对象也要保持状态，因此也应该在循环外定义。
      在此程序中使用bernoulli_distribution的一个原因是它允许我们调整选择先行一方的概率：[插图] bernoulli_distribution b(.55); // 给程序一个微小的优势
        如果b定义如上，则程序有55/45的机会先行。
    */
    bernoulli_distribution b(.55); // 给程序一个微小的优势；程序有55/45的机会先行。

    return 0;
}